package com.kizuki.algorithm.leetcode;

import java.util.LinkedList;

/**
 * 给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
 * 每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
 *
 * https://leetcode-cn.com/problems/maximum-width-of-binary-tree/
 * 本质就是层次遍历
 */
public class 二叉树最大宽度 {

    class Solution {

        public int widthOfBinaryTree(TreeNode root) {
            if (root == null) return 0;
            int res = 1;
            LinkedList<TreeNode> queue = new LinkedList<>();
            // 不修改原来的二叉树，记录节点的id
            LinkedList<Integer> ids = new LinkedList<>();
            queue.offer(root);
            ids.offer(1);
            while(!queue.isEmpty()) {
                int size = queue.size();
                res = Math.max(res, ids.peekLast() - ids.peekFirst() + 1);
                for (int i = 0; i < size; i++) {
                    TreeNode node = queue.pop();
                    Integer id = ids.poll();
                    if (node.left != null) {
                        queue.offer(node.left);
                        ids.offer(id * 2 + 1);
                    }
                    if (node.right != null) {
                        queue.offer(node.right);
                        ids.offer(id * 2 + 2);
                    }
                }
            }
            return res;
        }
    }
}
